P3657 Why Did the Cow Cross the Road II P

LCS是本题比较直观的一种思路，即将普通LCS（最长公共子序列）的相等的条件改为差的绝对值<=4

众所周知，求LCS有两种$O(nlogn)$方法

一种是映射，另一种是DP优化

因为差的绝对值<=4的条件会使映射变得复杂，我们这里采用DP优化的方法

该方法具体可以见[noip科普]关于LIS和一类可以用树状数组优化的DP

要注意的是，该方法中要记录b[]中各值可合法对应的值在a[]的位置，这个位置是需要通过排序来保证有序的

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}
const int N=1e5+5;
int a[N],b[N],n,f[N],ans,pos[N];
vector<int> p[N];
struct BIT{ //树状数组模板
    #define lowbit(x) (x&(-x))
    int a[N];
    void up(int x,int v){
        while(x<=n){
            a[x]=max(a[x],v);
            x+=lowbit(x);
        }
    }
    int que(int x){
        int res=0;
        while(x){
            res=max(res,a[x]);
            x-=lowbit(x);
        }
        return res;
    }
}ma;
signed main(){
    read(n);
    for(int i=1,x;i<=n;i++){
        read(x);
        pos[x]=i; //记录某值的位置
    }
    for(int i=1;i<=n;i++){
        read(b[i]);
        for(int j=max(1,b[i]-4);j<=min(n,b[i]+4);j++)
            p[i].push_back(pos[j]); //记录b[]值合法对应值的位置
        sort(p[i].begin(),p[i].end()); //排序使之保证有序
    }
    for(int i=1;i<=n;i++)
        for(int j=p[i].size()-1;j>=0;j--){ //按位置搞LCS
            int pos=p[i][j];
            f[pos]=ma.que(pos-1)+1;
            ma.up(pos,f[pos]);
        }
    for(int i=1;i<=n;i++) ans=max(ans,f[i]); //得到答案
    write(ans);
}